package BinaryTree.Medium;

public class LC1372 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int maxLevel = 0;

    public int longestZigZag(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null) dfs(root.left, false, 1);
        if (root.right != null) dfs(root.right, true, 1);
        return maxLevel;
    }

    private void dfs(TreeNode node, boolean turnLeft, int level) {
        if (node.left != null) {
            if (turnLeft) {
                maxLevel = Math.max(level + 1, maxLevel); // 向子结点扩展的过程中更新最长路径
                dfs(node.left, false, level + 1);
            }
            else {
                maxLevel = Math.max(1, maxLevel);
                dfs(node.left, false, 1);
            }
        }
        if (node.right != null) {
            if (!turnLeft) {
                maxLevel = Math.max(level + 1, maxLevel);
                dfs(node.right, true, level + 1);
            }
            else {
                maxLevel = Math.max(1, maxLevel);
                dfs(node.right, true, 1);
            }
        }
    }
}
